package com.jxb.e20241230;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum1_15 {

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        List<List<Integer>> lists = threeSum(nums);
        System.out.println(lists);
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        if (nums.length < 3) {
            return results;
        }
        //进行排序
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0;i<n;i++) {
            //若第一个数大于0，那么所有数都大于0
            if (nums[i] > 0) {
                break;
            }
            //定义双指针
            int head = i+1;
            int tail = n-1;
            //head和tail相向而行
            while (head < tail) {
                int sum = nums[i] + nums[head] + nums[tail];
                //小于0，左边元素太小需要往右移动
                if (sum < 0) {
                    head++;
                }
                //大于0，右边元素太大需要往左移动
                else if (sum > 0) {
                    tail--;
                }
                //相等，将数组进行记录
                else {
                    List<Integer> els = new ArrayList<>();
                    els.add(nums[i]);
                    els.add(nums[head]);
                    els.add(nums[tail]);
                    results.add(els);
                    //对head和head+1的元素相等进行去重
                    while (head + 1 <= tail && nums[head] == nums[head + 1]) {
                        head++;
                    }
                    //对tail和tail-1的元素相等进行去重
                    while (head + 1 <= tail && nums[tail] == nums[tail - 1]) {
                        tail--;
                    }
                    head++;
                    tail--;
                }
            }
            //对第一个元素重复，进行去重
            while (i+1 < n && nums[i+1] == nums[i]) {
                i++;
            }
        }
        return results;
    }
}
